/*
 * @lc app=leetcode.cn id=1034 lang=typescript
 *
 * [1034] 边框着色
 */

// @lc code=start
function colorBorder(grid: number[][], row: number, col: number, color: number): number[][] {
  const m = grid.length;
  const n = grid[0].length;
  // 4个方向
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  // 边框集合
  const borders = [];
  // 是否访问过
  const visited = new Array(m).fill(0).map(() => new Array(n).fill(0));
  // 连通分量的颜色
  const originColor = grid[row][col];
  // 初始点标记为已访问
  visited[row][col] = 1;

  // 深度优先搜索
  const dfs = (i: number, j: number) => {
    let isBorder = false;
    for (let k = 0; k < directions.length; k++) {
      const x = i + directions[k][0];
      const y = j + directions[k][1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] === originColor) {
        if (visited[x][y] === 0) {
          visited[x][y] = 1;
          dfs(x, y);
        }
      } else {
        isBorder = true;
      }
    }
    if (isBorder) borders.push([i, j]);
  };

  dfs(row, col);

  // 标记边框
  for (let i = 0; i < borders.length; i++) {
    const [x, y] = borders[i];
    grid[x][y] = color;
  }

  return grid;
}
// @lc code=end
